package sort;

import java.util.Arrays;

//选择排序时间复杂度为O(n^2),跟冒泡排序的时间复杂度一样,但排序速度比冒泡排序快
//基本思想是:每次排序中,都找出元素中最小的元素,然后放到最前面
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101,34,145,25,3};
        int index;//定义一个下标
        int min;//定义一个最小值
        //外层循环为排序次数,循环次数为数组元素个数减1
        for (int i = 0; i < arr.length-1; i++) {
             index = i;//本次排序中第一个元素的下标
             min = arr[index];//假定本次排序中第一个元素为最小值
            //内层循环为找出本次排序中最小的元素,并记录下这个最小值,以及这个最小值的下标
            for (int j = i+1; j < arr.length; j++) {
                if(min>arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            /*
            * 如果本排序中第一个元素下标没有发生变化,说明本次排序中的第一个元素就是本次排序的最小值
            * 那么这个元素就不用交换,否则把本次循环中的最小值和本次循环的第一个元素进行交换
            * */
            if(index != i) {
               arr[index]=arr[i];
               arr[i]=min;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
